(* Signature des elements *)
module type OrderedType =
sig
  type t
  val compare: t -> t -> int
end
 
(* Signature du resultat du foncteur *)
module type S =
sig
  type elm
  type t
  val empty : t
    (* ensemble vide *)
  val is_empty: t -> bool
    (* test du vide *)
  val cardinal: t -> int
    (* taille de l'ensemble *)
  val mem: elm -> t -> bool
    (* test d'appartenance *)
  val sub: t -> t -> bool
    (*
     * sub s1 s2 renvoie vrai si tous les elements de s1 sont dans s2
     *)
 
  val add: elm -> t -> t
    (*
     * add x s renvoie un nouvel ensemble contenant tous les elements
     * de s et x.
     * invariant: si s est trie sans doublon alors (add x s) est trie
     * sans doublon.
     * post-condition: mem x (add x s) renvoie vrai
     * post-condition: 0 <= (cardinal (add x s)) - (cardinal s) <= 1
     *)
 
  val union: t -> t -> t
    (*
     * union s1 s2 renvoie un nouvel ensemble contenant tous les
     * elements de s1 et tous les elements de s2.
     * invariant: si s1 et s2 sont tries sans doublon
     *            alors (union s1 s2) est trie sans doublon.
     * post-condition:
     *   cardinal (union s1 s2) <= cardinal s1 + cardinal s2
     *)
 
  val iter: (elm -> unit) -> t -> unit
    (*
     * iter f s applique la fonction f a tous les elements de s
     * les elements sont presentes dans l'ordre.
     *) 
end
 


module Make (T:OrderedType) =
struct
  type elm = T.t
  type t = elm list
 
  let empty =
	[]
  let is_empty s =
        s = []
  let rec cardinal = function
        | []                    	-> 0
        | h::q                  	-> 1 + cardinal q
  let rec mem elm = function
	| []				-> false
        | h::q when compare h elm = 0	-> true
        | _::q				-> false || (mem elm q)
  let rec sub s1 s2 =
	match s1 with
        | []                    	-> true
        | h::q                  	-> (mem h s2) && (sub q s2)
  let rec add elm = function
        | []                    	-> elm::[]
        | h::q when compare h elm = 0  	-> h::q
        | h::q when compare h elm > 0  	-> elm::h::q
        | h::q                  	-> h::add elm q
  let rec union s1 = function
        | []                    	-> s1
        | h::q                  	-> union (add h s1) q
  let rec iter f = function
        | []                    	-> ()
        | h::q                  	-> (f h);
					iter f q
end

